// 真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
/**
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个结点后，链表变为 1->2->3->5.
给定的 n 保证是有效的。
 */

/**
 * 思路：
 * 链表删除问题中，若走两次遍历，我们做了两件事：
1.求长度
2.做减法，找定位。

若用快慢指针，我们其实是把做减法和找定位这个过程给融合了。通过快指针先行一步、接着快慢指针一起前进这个操作，巧妙地把两个指针之间的差值保持在了“n”上（用空间换时间，本质上其实就是对关键信息进行提前记忆，这里咱们相当于用两个指针对差值实现了记忆），
这样当快指针走到链表末尾（第 len 个）时，慢指针刚好就在 len - n 这个地方稳稳落地。
 */
const Node = function (data) {
  this.val = data;
  this.next = null;
};
const node11 = new Node(1);
const node22 = new Node(2);
const node33 = new Node(3);
const node44 = new Node(4);
const node55 = new Node(5);
node11.next = node22;
node22.next = node33;
node33.next = node44;
node44.next = node55;

const removeNthFromEnd = function (head, n) {
  // 初始化 dummy 结点
  const dummy = new Node();
  // dummy指向头结点
  dummy.next = head;
  // 初始化快慢指针，均指向dummy
  let fast = dummy;
  let slow = dummy;

  // 快指针闷头走 n 步
  while (n !== 0) {
    fast = fast.next;
    n--;
  }

  // 快慢指针一起走
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }

  // 慢指针删除自己的后继结点
  slow.next = slow.next.next;
  // 返回头结点
  return dummy.next;
};
console.log(removeNthFromEnd(node11, 2));
